/**
 * 两个有序单链表A,B归并求交集，结果放在集合A中
 */
#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	struct LNode* next;
	int data;
} LNode, *LinkedList;

bool init(LinkedList &list);

bool insert(LinkedList &list, int data);

void print(LinkedList &list);

LinkedList _union(LinkedList &A, LinkedList &B);

int main()
{
	LinkedList A=NULL;
	LinkedList B=NULL;
	init(A);
	init(B);
	
	insert(A,1);
	insert(A,2);
	insert(A,4);
	insert(A,6);
	insert(A,7);
	insert(A,8);
	
	insert(B,0);
	insert(B,2);
	insert(B,3);
	insert(B,5);
	insert(B,7);
	insert(B,8);
	
	print(A);
	print(B);
	LinkedList unionA=_union(A,B);
	print(unionA);
	return 0;
}

bool init(LinkedList &list)
{
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	list=newNode;
	return true;
}

bool insert(LinkedList &list, int data)
{
	LinkedList node=list;
	while(node->next) node=node->next;
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	newNode->data=data;
	node->next=newNode;
	return true;
}

void print(LinkedList &list)
{
	LinkedList node=list->next;
	while(node)
	{
		printf("%d ",node->data);
		node=node->next;
	}
	printf("\n");
}

LinkedList _union(LinkedList &A, LinkedList &B)
{
	LNode* pa=A->next;	//pa为链表A的遍历结点
	LNode* pb=B->next;	//pb为链表B的遍历结点
	LNode* pc=A;		//pc指针指向结果表
	
	LNode* deleteNode=NULL;
	
	while(pa && pb)
	{
		if(pa->data==pb->data)
		{
			//找到公共结点
			pc->next=pa;
			pc=pa;
			
			pa=pa->next;
			deleteNode=pb;
			pb=pb->next;
			free(pb);
			deleteNode=NULL;
		} else if(pa->data < pb->data)	//A链表中的当前结点小于B链表中的当前结点
		{
			//要释放点A链表中的当前结点
			deleteNode=pa;
			pa=pa->next;
			free(deleteNode);
			deleteNode=NULL;
		}  else{//B链表中的当前结点小于A链表中的当前结点
			//要释放点A链表中的当前结点
			deleteNode=pb;
			pb=pb->next;
			free(deleteNode);
			deleteNode=NULL;
		}
	}
	
	while(pa)
	{
		//链表A中还有元素没有遍历，但是链表B已经遍历完了
		//需要把链表A剩下的元素全部删除，因为链表A不可能是链表A和链表B的公共结点了
		deleteNode=pa;
		pa=pa->next;
		free(deleteNode);
		deleteNode=NULL;
	}
	
	while(pb)
	{
		//链表B中还有元素没有遍历，但是链表A已经遍历完了
		//需要把链表B剩下的元素全部删除，因为链表B不可能是链表A和链表B的公共结点了
		deleteNode=pb;
		pb=pb->next;
		free(deleteNode);
		deleteNode=NULL;
	}
	return A;
}
